package leetcode.Hot100;

/**
 * @author Cheng Jun
 * Description: 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
 * 最大子序积
 * @version 1.0
 * @date 2021/11/24 17:08
 * 面试题
 */
public class maxProduct {

    public static void main(String[] args) {
        // System.out.println(maxProduct1(new int[]{2, 3, -2, 4}));
        // System.out.println(maxProduct0(new int[]{2, 3, -2, 4}));
        System.out.println(maxProduct1(new int[]{-4, -3, -2}));
        System.out.println(maxProduct0(new int[]{-4, -3, -2}));
    }

    // 根据正负性进行分类讨论。
    static int maxProduct0(int[] nums) {
        int ans = nums[0];
        int maxIndex = nums[0];
        int minIndex = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // 使用局部变量，避免计算错误
            int tempMaxIndex = maxIndex;
            int tempMinIndex = minIndex;
            maxIndex = Math.max(nums[i], Math.max(tempMaxIndex * nums[i], tempMinIndex * nums[i]));
            minIndex = Math.min(nums[i], Math.min(tempMaxIndex * nums[i], tempMinIndex * nums[i]));
            ans = Math.max(maxIndex, ans);
        }
        return ans;
    }

    // 两层for 循环，比较每个坐标作为起点，一直乘到最后一个数，这期间产生最大的数
    // 时间复杂度 n^2
    static int maxProduct1(int[] nums) {
        int max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            int indexMax = nums[i];
            max = Math.max(nums[i], max);
            if (nums[i] == 0) continue;
            for (int j = i + 1; j < nums.length; j++) {
                max = Math.max(indexMax * nums[j], max);
                indexMax *= nums[j];
                if (nums[j] == 0) break;
            }
        }
        return max;
    }

}
